// https://www.lintcode.com/problem/longest-consecutive-sequence/

public class Solution {
    /**
     * @param num: A list of integers
     * @return: An integer
     */
    public int longestConsecutive(int[] num) {
        // write your code here
        int ret = 0;
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i : num) {
            map.put(i, true);
        }
        for (int i : num) {
            if (map.containsKey(i) && map.get(i)) {
                int cnt = 1;
                int target = i + 1; // 向上找
                while (map.containsKey(target) && map.get(target)) {
                    map.put(target, false); // 标记已被使用
                    ++target;
                    ++cnt;
                }
                target = i - 1;
                while (map.containsKey(target) && map.get(target)) {
                    map.put(target, false); // 标记已被使用
                    --target;
                    ++cnt;
                }
                map.put(i, false);
                ret = Math.max(ret, cnt);
            }
        }
        return ret;
    }
}